#ifndef FIBONACCIHEAP_CPP
#define FIBONACCIHEAP_CPP

#include <cstddef>
#include <math.h>
#include <iostream>
#include "Queue.cpp"

using namespace std;

template <class T>
class FibonacciHeapNode
{
public:
    //data part
    T* dataLoad;
    unsigned int* key;
    FibonacciHeapNode** pointerStore;

    FibonacciHeapNode* child;
    FibonacciHeapNode* leftSibling;
    FibonacciHeapNode* rightSibling;
    bool childCut;
    int degree;
    FibonacciHeapNode* parent;

    FibonacciHeapNode ()
    {
        this->pointerStore = NULL;
        this->resetNode();
    }

    FibonacciHeapNode (T* data, unsigned int* keyPointer, FibonacciHeapNode** pointerStore)
    {
        this->initializeNode(data, keyPointer, pointerStore);
    }

    void initializeNode(T* data, unsigned int* keyPointer, FibonacciHeapNode** pointerStore)
    {
        this->dataLoad = data;
        this->key = keyPointer;
        this->parent = NULL;
        this->degree = 0;
        this->child = NULL;
        this->childCut = false;
        this->leftSibling = this;
        this->rightSibling = this;
        this->pointerStore = pointerStore;
        this->setPointerStore();
    }

    void resetNode()
    {
        this->dataLoad = NULL;
        this->key = NULL;
        this->parent = NULL;
        this->degree = 0;
        this->child = NULL;
        this->childCut = false;
        this->leftSibling = this;
        this->rightSibling = this;
        this->setPointerStoreNULL();
        this->pointerStore = NULL;
    }

    void setPointerStore()
    {
        if (this->pointerStore != NULL)
        {
            //cout<<"\nnode pointer value old: "<<*(this->pointerStore)<<" new: "<<this;
            *(this->pointerStore) = this;
        }
    }

    void setPointerStoreNULL()
    {
        if (this->pointerStore != NULL)
        {
            //cout<<"\nnode pointer value old: "<<*(this->pointerStore)<<" new: "<<NULL;
            *(this->pointerStore) = NULL;
        }
    }
};

template <class T>
class FibonacciHeap
{
public:
    FibonacciHeapNode<T>* head;

    FibonacciHeap();
    ~FibonacciHeap();
    FibonacciHeapNode<T>* insert (T* data, unsigned int* keyPointer, FibonacciHeapNode<T>** pointerStore);
    FibonacciHeapNode<T>* insert (T* data, unsigned int* keyPointer);
    FibonacciHeapNode<T>* getHead ();
    void meld (FibonacciHeap<T>* node);
    T* removeMin();
    void decreaseKey(FibonacciHeapNode<T>* node, unsigned int newKeyVal);
    void displayBFS ();
    void displayDFS ();
    int getNumberOfNodes();
    void remove (FibonacciHeapNode<T>* node);
    void emptyIt();

private:
    int numberOfNodes;
    FibonacciHeapNode<T>* freeNodes;
    static const unsigned int maxNumberOfFreeNodes = 600;   //class constant
    int numberOfFreeNodes;
    FibonacciHeapNode<T>** treeDeg;

    FibonacciHeapNode<T>* getFreeNode (T* data, unsigned int* keyPointer, FibonacciHeapNode<T>** pointerStore);
    void releaseNode (FibonacciHeapNode<T>* node);
    void releaseHeap (FibonacciHeapNode<T>* node);
    void meld (FibonacciHeapNode<T>* node);
    void displayDFS(FibonacciHeapNode<T>* node);
    void cascadingCut(FibonacciHeapNode<T>* parentNode);
    FibonacciHeapNode<T>* meld(FibonacciHeapNode<T>* node, FibonacciHeapNode<T>* node1);
    void pairwiseCombine ();
    void disconnectFromParent(FibonacciHeapNode<T>* node);
    void disconnectFromSiblings(FibonacciHeapNode<T>* node);
};

template<class T>
FibonacciHeapNode<T>* FibonacciHeap<T>::getFreeNode(T* data, unsigned int* keyPointer, FibonacciHeapNode<T>** pointerStore)
{
    if (this->freeNodes == NULL)
    {
        return NULL;
    }
    FibonacciHeapNode<T>* temp = this->freeNodes;
    this->freeNodes = this->freeNodes->rightSibling;
    temp->initializeNode(data, keyPointer, pointerStore);
    this->numberOfFreeNodes--;
    return temp;
}

template<class T>
void FibonacciHeap<T>::releaseNode(FibonacciHeapNode<T>* node)
{
    if (node == NULL)
    {
        return;
    }
    node->resetNode();
    node->rightSibling = this->freeNodes;
    this->numberOfFreeNodes++;
    this->freeNodes = node;
}

template<class T>
void FibonacciHeap<T>::releaseHeap(FibonacciHeapNode<T>* node)
{
    FibonacciHeapNode<T>* temp = node;
    while (node != NULL)
    {
        if (node->child != NULL)
        {
            this->releaseHeap(node->child);
        }
        temp = node;
        node = node->rightSibling;
        this->releaseNode(temp);
    }
}

template<class T>
void FibonacciHeap<T>::emptyIt()
{
    FibonacciHeapNode<T>* temp = NULL;
    this->releaseHeap(this->head);
    this->head = NULL;
    this->numberOfNodes = 0;
    //this->numOfFreeNodes = 600;
}

template <class T>
void FibonacciHeap<T>::remove (FibonacciHeapNode<T>* node)
{
    //delete the node merge the child to the top level list and do a cascading cut
    if (node == NULL)
    {
        return;
    }
    if (node == this->head)
    {
        this->removeMin();
        return;
    }
    FibonacciHeapNode<T>* tempChild = node->child;
    FibonacciHeapNode<T>* tempParent = node->parent;
    this->disconnectFromParent (tempChild);
    this->disconnectFromSiblings (node);
    FibonacciHeapNode<T>* temp = tempChild;
    do
    {
        temp->parent = NULL;
        temp = temp->rightSibling;
    } while (temp != tempChild);
    this->meld (tempChild);
    this->cascadingCut(tempParent);
}

template<class T>
void FibonacciHeap<T>::displayDFS()
{
    FibonacciHeapNode<T>* temp = this->getHead();
    if (temp == NULL)
    {
        return;
    }
    this->displayDFS (this->getHead());
}

template<class T>
void FibonacciHeap<T>::displayDFS (FibonacciHeapNode<T>* node)
{
    if (node == NULL)
    {
        return;
    }
    FibonacciHeapNode<T>* temp = node;
    int parent = (node->parent != NULL)? *(node->parent->key) : 0;
    do
    {
        cout<<"("<<parent<<", "<<*(temp->key)<<")\t";
        displayDFS (temp->child);
    } while (temp != node);
}

//BFS
template<class T>
void FibonacciHeap<T>::displayBFS()
{
    Queue<FibonacciHeapNode<T> >* masterQueue = new Queue<FibonacciHeapNode<T> >();
    Queue<FibonacciHeapNode<T> >* slaveQueue = new Queue<FibonacciHeapNode<T> >();
    if (this->head == NULL)
    {
        cout<<"\n\n<<<<Heap Empty!!!>>>>";
        return;
    }
    cout<<"\nHead is "<<*(this->head->key);
    slaveQueue->enqueue(this->getHead());
    int count = 0;
    FibonacciHeapNode<T>* temp = NULL;
    cout<<endl<<"\nNumber of nodes in this heap: "<<this->numberOfNodes;
    do
    {
        delete (masterQueue);
        masterQueue = slaveQueue;
        slaveQueue = new Queue<FibonacciHeapNode<T> >();
        cout<<endl<<endl<<"Level "<<count++<<"\t";
        while ((temp = masterQueue->dequeue()) != NULL)
        {
            //cout<<"\nMaster Dequeue: "<<*temp->key;
            int parentKey = (temp->parent != NULL) ? *(temp->parent->key) : 0;
            FibonacciHeapNode<T>* temp1 = temp;
            do
            {
                cout<<"("<<parentKey<<", "<<*(temp1->key)<<")\t";
                if (temp1->child != NULL)
                {
                    //cout<<"\nSlave Enqueue: "<<*temp1->child->key;
                    slaveQueue->enqueue(temp1->child);
                }
                temp1 = temp1->rightSibling;
            } while (temp1 != temp);
        }
    } while (slaveQueue->hasElements());
}

template<class T>
void FibonacciHeap<T>::decreaseKey(FibonacciHeapNode<T>* node, unsigned int newKeyVal)
{
    //false condis
    if (node == NULL || newKeyVal > *(node->key))
    {
        cout<<"FaultCondis of decrease key";
        return;
    }
    *(node->key) = newKeyVal;
    if (node->parent != NULL && *(node->key) > *(node->parent->key))
    {
        return; //no heap property distroyed
    }
    else if (node->parent == NULL)
    {
        if (*(this->head->key) > *(node->key))
        {
            //if one of the top level node then update the head and return
            this->head = node;
        }
        return;
    }

    FibonacciHeapNode<T>* tempParent = node->parent;
    this->disconnectFromParent (node);
    this->disconnectFromSiblings(node);
    this->meld(node);
    this->cascadingCut (tempParent);
}

template <class T>
void FibonacciHeap<T>::cascadingCut(FibonacciHeapNode<T>* parentNode)
{
    if (parentNode == NULL)
    {
        return;     //null node nothing can be done
    }
    //     its not top level node     && its child cut is true
    while (parentNode->parent != NULL && parentNode->childCut == true)
    {
        FibonacciHeapNode<T>* temp = parentNode;
        parentNode = parentNode->parent;
        this->disconnectFromParent(temp);
        this->disconnectFromSiblings(temp);
        temp->childCut = false;
        this->meld(temp);
    }
    if (parentNode->parent != NULL)
    {
        parentNode->childCut = true;
    }
}

//doesnt change the childCut value of parent
template<class T>
void FibonacciHeap<T>::disconnectFromParent(FibonacciHeapNode<T>* node)
{
    //disconnecting from parent
    FibonacciHeapNode<T>* tempParent = node->parent;
    if (tempParent != NULL)
    {
        tempParent->degree--;
        node->parent = NULL;

        if (tempParent->child == node)  //if child is the node getting disconnected
        {
            if (node == node->rightSibling) //only one in child list
            {
                tempParent->child = NULL;
            }
            else
            {
                tempParent->child = node->rightSibling;
            }
        }
    }
}

template<class T>
void FibonacciHeap<T>::disconnectFromSiblings(FibonacciHeapNode<T>* node)
{
    //disconnecting from sibling
    node->rightSibling->leftSibling = node->leftSibling;
    node->leftSibling->rightSibling = node->rightSibling;
    node->rightSibling = node;
    node->leftSibling = node;
}

template<class T>
T* FibonacciHeap<T>::removeMin()
{
    if (this->head == NULL)
    {
        //cout<<"remove fail";
        return NULL;
    }
    T* minData = head->dataLoad;
    FibonacciHeapNode<T>* headChild = this->head->child;
    this->head->child = NULL;

    //Only node in the parent list
    if (this->head == this->head->rightSibling)
    {
        FibonacciHeapNode<T>* temp = this->head;
        this->releaseNode(temp);
        this->head = NULL;
    }
    else
    {
        FibonacciHeapNode<T>* temp = this->head;
        this->head = this->head->rightSibling;   //nextHead may not be minimum //just assign something... Pairwise combine will take care of minimum property
        this->disconnectFromSiblings(temp);
        this->releaseNode(temp);
    }
    if (headChild != NULL)
    {
        this->meld(headChild);  //remember to set parent of every top level nodes to NULL in pairwise combine
    }
    this->pairwiseCombine();
    this->numberOfNodes--;
    return minData;
}

template<class T>
void FibonacciHeap<T>::pairwiseCombine ()
{
    //this->displayBFS();
    //Only 0/1 Binomial-Tree no need of pairwise Combine
    if (this->head == NULL)
    {
        return;
    }
    else if (this->head == this->head->rightSibling)
    {
        this->head->parent = NULL;
        return;
    }

    int n = (log((double)(this->numberOfNodes * sqrt((double)5))) / log( (1 + sqrt((double)5) ) / 2)) + 3;
    //int n = this->numberOfNodes; //dont have information about max degree of node
    for (int i =0 ;i<n; i++)
    {
        treeDeg[i] = NULL;
    }
    FibonacciHeapNode<T>* node = this->head->rightSibling;

    //adding first one to treedeg
    this->head->rightSibling = this->head;	//disconnecting
    this->head->leftSibling = this->head;	//disconnecting
    this->head->parent = NULL;	//top level so ensuring its parent is null
    treeDeg[this->head->degree] = this->head;	//inserting on treeDeg

    while (node != this->head)
    {
        FibonacciHeapNode<T>* nextNode = node->rightSibling;	//storing the next pointer

        node->rightSibling = node;	//disconnecting
        node->leftSibling = node;	//disconnecting

        while (treeDeg[node->degree] != NULL)
        {
            FibonacciHeapNode<T>* node1 = treeDeg[node->degree];
            treeDeg[node->degree] = NULL;   //removing it from the deg Array
            if (*(node1->key) < *(node->key))   //ensuring node has smaller value
            {
                FibonacciHeapNode<T>* tNode = node1;
                node1 = node;
                node = tNode;
            }
            node->degree++;
            node1->childCut = false;
            node->child = this->meld(node->child, node1);
            node1->parent = node;
            node->parent = NULL;
        }
        treeDeg[node->degree] = node;   //put it back into deg list
        node = nextNode;
    }
    FibonacciHeapNode<T>* tempNode = NULL;
    FibonacciHeapNode<T>* firstTempNode = NULL;
    for (int i=0; i<n; i++)
    {
        if (treeDeg[i] != NULL)
        {

            if (tempNode == NULL)
            {
                this->head = treeDeg[i];
                firstTempNode = treeDeg[i];
                tempNode = treeDeg[i];
                tempNode->parent = NULL;
            }
            else
            {
                if (*(this->head->key) > *(treeDeg[i]->key))
                {
                    this->head = treeDeg[i];
                }
                tempNode->rightSibling = treeDeg[i];
                treeDeg[i]->leftSibling = tempNode;
                tempNode = treeDeg[i];
                tempNode->parent = NULL;
            }
        }
    }
    tempNode->rightSibling = firstTempNode;
    firstTempNode->leftSibling = tempNode;
}

template<class T>
void FibonacciHeap<T>::meld (FibonacciHeap<T>* heap)
{
    if (heap == NULL)
    {
        return;
    }
    this->numberOfNodes += heap->numberOfNodes;
    this->meld(heap->getHead());
}

//in meld its expected to be a binomial heap so node will point to the min element of the next binomial heap
template<class T>
void FibonacciHeap<T>::meld(FibonacciHeapNode<T>* node)
{
    this->head = this->meld(this->head, node);
}

template<class T>
FibonacciHeapNode<T>* FibonacciHeap<T>::meld(FibonacciHeapNode<T>* node, FibonacciHeapNode<T>* node1)
{
    if (node == NULL || node1 == NULL)
    {
        if (node != NULL)
        {
            return node;
        }
        else if (node1 != NULL)
        {
            return node1;
        }
    }
    FibonacciHeapNode<T>* nextNode1 = node1->rightSibling;
    FibonacciHeapNode<T>* nextNode = node->rightSibling;
    node->rightSibling = nextNode1;
    nextNode1->leftSibling = node;
    node1->rightSibling = nextNode;
    nextNode->leftSibling = node1;
    if (*node->key < *node1->key)
    {
        return node;
    }
    return node1;
}

template<class T>
FibonacciHeapNode<T>* FibonacciHeap<T>::getHead()
{
    return this->head;
}

template<class T>
FibonacciHeap<T>::FibonacciHeap()
{
    this->head = NULL;
    this->numberOfNodes = 0;
    this->freeNodes = NULL;
    this->treeDeg = new FibonacciHeapNode<T>*[FibonacciHeap::maxNumberOfFreeNodes];
    this->numberOfFreeNodes = FibonacciHeap::maxNumberOfFreeNodes;
    for (int i=0; i<FibonacciHeap::maxNumberOfFreeNodes; i++)
    {
        FibonacciHeapNode<T>* temp = new FibonacciHeapNode<T>();
        temp->rightSibling = this->freeNodes;
        this->freeNodes = temp;
    }
}

template<class T>
FibonacciHeap<T>::~FibonacciHeap()
{
    delete[] this->treeDeg;
    this->releaseHeap(this->head);
    FibonacciHeapNode<T>* temp = this->freeNodes;
    while (temp != NULL)
    {
        FibonacciHeapNode<T>* temp1 = temp;
        temp = temp->rightSibling;
        delete (temp1);
    }
}

template<class T>
FibonacciHeapNode<T>* FibonacciHeap<T>::insert(T* data, unsigned int* keyPointer)
{
    return this->insert(data, keyPointer, NULL);
}

//Give in the data and key it will create a new node and meld
template<class T>
FibonacciHeapNode<T>* FibonacciHeap<T>::insert(T* data, unsigned int* keyPointer, FibonacciHeapNode<T>** pointerStore)
{
    FibonacciHeapNode<T>* node = this->getFreeNode(data, keyPointer, pointerStore);     //new FibonacciHeapNode<T>(data, keyPointer, pointerStore);
    this->numberOfNodes++;
    this->meld (node);
    return node;
}

template<class T>
int FibonacciHeap<T>::getNumberOfNodes()
{
    return this->numberOfNodes;
}


#endif
